package demo.practice.dp;

public class P297 {

    public static void main(String[] args) {
        Solution solution= new Solution();
        solution.numSquares(1);
    }

    static class Solution {


        public int numSquares(int n) {
            //使用动态规划
            //dp[n]= Min(f[n-j*j]+1 )

            int dp[] = new int[n + 1];
            dp[0] = 0;
            for (int i = 1; i <=n; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = 1; j * j <=i; j++) {
                    dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
                }
            }

            return dp[n];
        }
    }
}
